package com.leetcode.www;

import java.util.Arrays;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个长度为 n 的整数数组nums。
 *
 * 假设arrk是数组nums顺时针旋转 k 个位置后的数组，我们定义nums的 旋转函数F为：
 *
 * F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
 * 返回F(0), F(1), ..., F(n-1)中的最大值。
 *
 * 生成的测试用例让答案符合32 位 整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-function
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-22
 * Time:17:49
 */
public class Everyday396 {
    public int maxRotateFunction(int[] nums) {//滑动窗口
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
        for (int i = n + 1, cur = ans; i < 2 * n; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) ans = cur;
        }
        return ans;
    }
    public int maxRotateFunction2(int[] nums) {
        int f = 0;
        int n = nums.length;
        int numSum = Arrays.stream(nums).sum();//迭代求和
        for (int i = 0; i < n; i++) {
            f += i * nums[i];//先算出按正常顺序的出的和
        }
        int res = f;
        for (int i = n - 1; i > 0; i--) {
            f += numSum - n * nums[i];//用所有数的总和减去每一个值旋转到最后一个值的情况,从中取到最大值
            res = Math.max(res, f);
        }
        return res;
    }
    public int maxRotateFunction1(int[] nums) {//这样做时间复杂度会高
        int n = nums.length;
        if(n == 1){
            return 0;
        }


        int count = Integer.MIN_VALUE;//存放最大值
        //第一个元素乘0,第二次第一个元素乘1,
        for(int i = 0;i < n;i ++){
            int sum = 0;//相加求和
            int a = i;
            for(int j = 0;j < n;j ++){

                int x = a * nums[j];
                a = (a + 1) % n;
                sum += x;
            }
            count = Math.max(count,sum);
        }
        return count;
    }

}
